/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode LTNode;   
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    LTNode* dummy = (LTNode*)malloc(sizeof(LTNode));
    dummy->val = 0;
    dummy->next = NULL;

    LTNode*  cur = dummy;
    while (list1 && list2)
    {
        int val = 0;
        if (list1->val < list2->val)
        {
            val = list1->val;
            list1 = list1->next;
            printf(">\n");
        }
        else
        {
            val = list2->val;
            list2 = list2->next;
            printf("<=\n");
        }
        cur->next = (LTNode*)malloc(sizeof(LTNode)); 
        cur->next->val = val;
        cur->next->next = NULL;
        cur = cur->next;
    }
    while (list1)
    {
        cur->next = (LTNode*)malloc(sizeof(LTNode)); 
        cur->next->val = list1->val;
        cur->next->next = NULL;
        cur = cur->next;     
        list1 = list1->next;   
    }
    while (list2)
    {
        cur->next = (LTNode*)malloc(sizeof(LTNode)); 
        cur->next->val = list2->val;
        cur->next->next = NULL;
        cur = cur->next;     
        list2 = list2->next;   
    }    
    return dummy->next;
}